L'algorithme de \tsl{branch \& bound} est le plus compliqué des trois. En
effet, il suppose d'abord d'implémenter un \tsl{backtracking} puis de pruner
chaque sous arbre de solution si la surestimation du revenu que nous en
faisons n'est pas au moins meilleurs que la meilleurs de nos solution.

L'analyse de ce genre d'algorithme est encore sujet à une recherche active et
nous ne pourrons bien entendu donner que quelques éléments de la complexité
asymptotique.

\paragraph{Backtracking : Recherche exhaustive}
Le backtracking consiste à générer toutes les solutions possibles en éliminant à
chaque pas les sous arbres de solutions qui ne peuvent pas fournir une
solution respectant les contraintes du problème (en l'occurrence la capacité
de la station principale). La complexité d'une telle approche en pire cas est
donc le nombre de permutations possibles de l'arrangement, \tsl{i.e.} :
$$O(n!)$$

Cette complexité est simplement inexploitable en pratique et il faut
impérativement réduire l'espace des solutions possibles.

\paragraph{Pruning}
Pour cela, nous disposons d'une solutions à priori suboptimale qui pourrait
nous permettre de réduire notre espace de recherche. Cela nécessite tout de
même de pouvoir "completer" notre solution, ce qui est le cas ici. La figure
\ref{fig:bb} illustre le pruning d'un arbre de solution dans le cas du
problème du sac à dos.

\begin{figure}[H]
\begin{center}
  \includegraphics[width=.5\textwidth]{img/bb}
  \caption{Exemple de branch \& bound\label{fig:bb}}
\end{center}
\end{figure}

Nous avons donc un algorithme du type :
\code[C++]{}{code/b8b.cc}

Étonnement, l'algorithme est très simple. Récursivement, si la solution est
prometteuse, alors générer les sous arbres, sinon, abandonner la solution. 

\paragraph{Conclusion}
Bien qu'il soit impossible de faire une analyse mathématique de la récurrence
(à cause des branchements), nous pouvons affirmer que la complexité sera au
moins inférieure à celle d'un backtracking récursif sans critère d'abandon des
sous arbres :
$$\mbox{Temps, en pire cas : } T(n) \leq O(n!)$$
$$\mbox{Espace, dans tous les cas : } \Theta(n)$$
